home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / documents / RFC / rfc1266.txt < prev    next >
Text File  |  1994-08-01  |  22KB  |  507 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                 Y. Rekhter, Editor
  8. Request for Comments: 1266        T.J. Watson Research Center, IBM Corp.
  9.                                                             October 1991
  10.  
  11.  
  12.                     Experience with the BGP Protocol
  13.  
  14. 1. Status of this Memo.
  15.  
  16.    This memo provides information for the Internet community.  It does
  17.    not specify an Internet standard. Distribution of this memo is
  18.    unlimited.
  19.  
  20. 2. Introduction.
  21.  
  22.    The purpose of this memo is to document how the requirements for
  23.    advancing a routing protocol to Draft Standard have been satisfied by
  24.    Border Gateway Protocol (BGP). This report documents experience with
  25.    BGP.  This is the second of two reports on the BGP protocol.  As
  26.    required by the Internet Activities Board (IAB) and the Internet
  27.    Engineering Steering Group (IESG), the first report will present a
  28.    performance analysis of the BGP protocol.
  29.  
  30.    The remaining sections of this memo document how BGP satisfies
  31.    General Requirements specified in Section 3.0, as well as
  32.    Requirements for Draft Standard specified in Section 5.0 of the
  33.    "Internet Routing Protocol Standardization Criteria" document [1].
  34.  
  35.    This report is based on the work of Dennis Ferguson (University of
  36.    Toronto), Susan Hares (MERIT/NSFNET), and Jessica Yu (MERIT/NSFNET).
  37.    Details of their work were presented at the Twentieth IETF meeting
  38.    (March 11-15, 1991, St. Louis) and are available from the IETF
  39.    Proceedings.
  40.  
  41.    Please send comments to iwg@rice.edu.
  42.  
  43. 3. Acknowledgements.
  44.  
  45.    The BGP protocol has been developed by the IWG/BGP Working Group of
  46.    the Internet Engineering Task Force. We would like to express our
  47.    deepest thanks to Guy Almes (Rice University) who was the previous
  48.    chairman of the IWG Working Group.  We also like to explicitly thank
  49.    Bob Hinden (BBN) for the review of this document as well as his
  50.    constructive and valuable comments.
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58. BGP Working Group                                               [Page 1]
  59.  
  60. RFC 1266            Experience with the BGP Protocol        October 1991
  61.  
  62.  
  63. 4. Documentation.
  64.  
  65.    BGP is an inter-autonomous system routing protocol designed for the
  66.    TCP/IP internets.  Version 1 of the BGP protocol was published in RFC
  67.    1105. Since then BGP Versions 2 and 3 have been developed. Version 2
  68.    was documented in RFC 1163. Version 3 is documented in [3]. The
  69.    changes between versions 1, 2 and 3 are explained in Appendix 3 of
  70.    [3].  Most of the functionality that was present in the Version 1 is
  71.    present in the Version 2 and 3.  Changes between Version 1 and
  72.    Version 2 affect mostly the format of the BGP messages.  Changes
  73.    between Version 2 and Version 3 are quite minor.
  74.  
  75.    BGP Version 2 removed from the protocol the concept of "up", "down",
  76.    and "horizontal" relations between autonomous systems that were
  77.    present in the Version 1.  BGP Version 2 introduced the concept of
  78.    path attributes.  In addition, BGP Version 2 clarified parts of the
  79.    protocol that were "underspecified".  BGP Version 3 lifted some of
  80.    the restrictions on the use of the NEXT_HOP path attribute, and added
  81.    the BGP Identifier field to the BGP OPEN message. It also clarifies
  82.    the procedure for distributing BGP routes between the BGP speakers
  83.    within an autonomous system.  Possible applications of BGP in the
  84.    Internet are documented in [2].
  85.  
  86.    The BGP protocol was developed by the IWG/BGP Working Group of the
  87.    Internet Engineering Task Force. This Working Group has a mailing
  88.    list, iwg@rice.edu, where discussions of protocol features and
  89.    operation are held. The IWG/BGP Working Group meets regularly during
  90.    the quarterly Internet Engineering Task Force conferences. Reports of
  91.    these meetings are published in the IETF's Proceedings.
  92.  
  93. 5. MIB
  94.  
  95.    A BGP Management Information Base has been published [4].  The MIB
  96.    was written by Steve Willis (swillis@wellfleet.com) and John Burruss
  97.    (jburruss@wellfleet.com).
  98.  
  99.    Apart from a few system variables, the BGP MIB is broken into two
  100.    tables: the BGP Peer Table and the BGP Received Path Attribute Table.
  101.    The Peer Table reflects information about BGP peer connections, such
  102.    as their state and current activity. The Received Path Attribute
  103.    Table contains all attributes received from all peers before local
  104.    routing policy has been applied. The actual attributes used in
  105.    determining a route are a subset of the received attribute table.
  106.  
  107.    The BGP MIB is quite small. It contains total of 27 objects.
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114. BGP Working Group                                               [Page 2]
  115.  
  116. RFC 1266            Experience with the BGP Protocol        October 1991
  117.  
  118.  
  119. 6. Security architecture.
  120.  
  121.    BGP provides flexible and extendible mechanism for authentication and
  122.    security. The mechanism allows to support schemes with various degree
  123.    of complexity. All BGP sessions are authenticated based on the BGP
  124.    Identifier of a peer. In addition, all BGP sessions are authenticated
  125.    based on the autonomous system number advertised by a peer. As part
  126.    of the BGP authentication mechanism, the protocol allows to carry
  127.    encrypted digital signature in every BGP message. All authentication
  128.    failures result in sending the NOTIFICATION messages and immediate
  129.    termination of the BGP connection.
  130.  
  131.    Since BGP runs over TCP and IP, BGP's authentication scheme may be
  132.    augmented by any authentication or security mechanism provided by
  133.    either TCP or IP.
  134.  
  135. 7. Implementations.
  136.  
  137.    There are multiple interoperable implementations of BGP currently
  138.    available. This section gives a brief overview of the three
  139.    completely independent implementations that are currently used in the
  140.    operational Internet. They are:
  141.  
  142.       - cisco. This implementation was wholly developed by cisco.
  143.         It runs on the proprietary operating system used by the
  144.         cisco routers. Consult Kirk Lougheed (lougheed@cisco.com)
  145.         for more details.
  146.  
  147.       - "gated". This implementation was developed wholly by Jeff
  148.         Honig (jch@risci.cit.cornell.edu) and Dennis Ferguson
  149.         (dennis@CAnet.CA).  It runs on a variety of operating systems
  150.         (4.3 BSD, AIX, etc...).  It is the only available public domain
  151.         code for BGP. Consult Jeff Honig or Dennis Ferguson for more
  152.         details.
  153.  
  154.       - NSFNET. This implementation was developed wholly by Yakov
  155.         Rekhter (yakov@watson.ibm.com). It runs on the T1 NSFNET
  156.         Backbone and T3 NSFNET Backbone. Consult Yakov Rekhter for
  157.         more details.
  158.  
  159.    To facilitate efficient BGP implementations, and avoid commonly made
  160.    mistakes, the implementation experience with BGP in "gated" was
  161.    documented as part of RFC 1164.  Implementors are strongly encouraged
  162.    to follow the implementation suggestions outlined in that document.
  163.  
  164.    Experience with implementing BGP showed that the protocol is
  165.    relatively simple to implement. On the average BGP implementation
  166.    takes about 1 man/month effort.
  167.  
  168.  
  169.  
  170. BGP Working Group                                               [Page 3]
  171.  
  172. RFC 1266            Experience with the BGP Protocol        October 1991
  173.  
  174.  
  175.    Note that, as required by the IAB/IESG for Draft Standard status,
  176.    there are multiple interoperable completely independent
  177.    implementations, namely those from cisco, "gated", and IBM.
  178.  
  179. 8. Operational experience.
  180.  
  181.    This section discusses operational experience with BGP.
  182.  
  183.    BGP has been used in the production environment since 1989.  This use
  184.    involves all three implementations listed above.  Production use of
  185.    BGP includes utilization of all significant features of the protocol.
  186.    The present production environment, where BGP is used as the inter-
  187.    autonomous system routing protocol, is highly heterogeneous.  In
  188.    terms of the link bandwidth it varies from 56 Kbits/sec to 45
  189.    Mbits/sec. In terms of the actual routes that run BGP it ranges from
  190.    a relatively slow performance PC/RT to a very high performance
  191.    RS/6000, and includes both the special purpose routers (cisco) and
  192.    the general purpose workstations running UNIX. In terms of the actual
  193.    topologies it varies from a very sparse (spanning tree or a ring of
  194.    CA*Net) to a quite dense (T1 or T3 NSFNET Backbones).
  195.  
  196.    At the time of this writing BGP is used as an inter-autonomous system
  197.    routing protocol between the following autonomous systems: CA*Net, T1
  198.    NSFNET Backbone, T3 NSFNET Backbone, T3 NSFNET Test Network, CICNET,
  199.    MERIT, and PSC. Within CA*Net there are 10 border routers
  200.    participating in BGP. Within T1 NSFNET Backbone there are 20 border
  201.    routers participating in BGP. Within T3 NSFNET Backbone there are 15
  202.    border routers participating in BGP. Within T3 NSFNET Test Network
  203.    there are 7 border routers participating in BGP. Within CICNET there
  204.    are 2 border routers participating in BGP. Within MERIT there is 1
  205.    border router participating in BGP. Within PSC there is 1 router
  206.    participating in BGP. All together there are 56 border routers
  207.    spanning 7 autonomous systems that are running BGP.  Out of these, 49
  208.    border routers that span 6 autonomous systems are part of the
  209.    operational Internet.
  210.  
  211.    BGP is used both for the exchange of routing information between a
  212.    transit and a stub autonomous system, and for the exchange of routing
  213.    information between multiple transit autonomous systems. It covers
  214.    both the Backbones (CA*Net, T1 NSFNET Backbone, T3 NSFNET Backbone),
  215.    and the Regional Networks (PSC, MERIT).
  216.  
  217.    Within CA*Net, T3 NSFNET Backbone, and T3 NSFNET Test Network BGP is
  218.    used as the exclusive carrier of the exterior routing information
  219.    both between the autonomous systems that correspond to the above
  220.    networks, and with the autonomous system of each network. At the time
  221.    of this writing within the T1 NSFNET Backbone BGP is used together
  222.    with the NSFNET Backbone Interior Routing Protocol to carry the
  223.  
  224.  
  225.  
  226. BGP Working Group                                               [Page 4]
  227.  
  228. RFC 1266            Experience with the BGP Protocol        October 1991
  229.  
  230.  
  231.    exterior routing information. T1 NSFNET Backbone is in the process of
  232.    moving toward carrying the exterior routing information exclusively
  233.    by BGP.  The full set of exterior routes that is carried by BGP is
  234.    well over 2,000 networks.
  235.  
  236.    Operational experience described above involved multi-vendor
  237.    deployment (cisco, "gated", and NSFNET).
  238.  
  239.    Specific details of the operational experience with BGP in the NSFNET
  240.    were presented at the Twentieth IETF meeting (March 11-15, 1991, St.
  241.    Louis) by Susan Hares (MERIT/NSFNET).  Specific details of the
  242.    operational experience with BGP in the CA*Net were presented at the
  243.    Twentieth IETF meeting (March 11-15, 1991, St. Louis) by Dennis
  244.    Ferguson (University of Toronto).  Both of these presentations are
  245.    available in the IETF Proceedings.
  246.  
  247.    Operational experience with BGP exercised all basic features of the
  248.    protocol, including the authentication and routing loop suppression.
  249.  
  250.    Bandwidth consumed by BGP has been measured at the interconnection
  251.    points between CA*Net and T1 NSFNET Backbone. The results of these
  252.    measurements were presented by Dennis Ferguson during the last IETF,
  253.    and are available from the IETF Proceedings. These results showed
  254.    clear superiority of BGP as compared with EGP in the area of
  255.    bandwidth consumed by the protocol. Observations on the CA*Net by
  256.    Dennis Ferguson, and on the T1 NSFNET Backbone by Susan Hares
  257.    confirmed clear superiority of BGP as compared with EGP in the area
  258.    of CPU requirements.
  259.  
  260. 9. Using TCP as a transport for BGP.
  261.  
  262. 9.1. Introduction.
  263.  
  264.    On multiple occasions some members of IETF expressed concern about
  265.    using TCP as a transport protocol for BGP. In this section we examine
  266.    the use of TCP for BGP in terms of:
  267.  
  268.       - real versus perceived problems
  269.       - offer potential solutions to real problems
  270.       - perspective on the convergence problem
  271.       - conclusions
  272.  
  273.    BGP is based on the incremental updates. This is done intentionally
  274.    to conserve the CPU and bandwidth requirements. Extensive operational
  275.    experience with BGP in the Internet showed that indeed the use of the
  276.    incremental updates allows significant saving both in terms of the
  277.    CPU utilization and bandwidth consumption.  However, to operate
  278.    correctly the incremental updates must be exchanged over a reliable
  279.  
  280.  
  281.  
  282. BGP Working Group                                               [Page 5]
  283.  
  284. RFC 1266            Experience with the BGP Protocol        October 1991
  285.  
  286.  
  287.    transport.  BGP uses TCP as such transport. It had been suggested
  288.    that another transport protocol would be more suitable for BGP.
  289.  
  290. 9.2. Examination of Problems - Real and "perceived".
  291.  
  292.    Extensive operational experience with BGP in the Internet showed that
  293.    the only real problem that was attributed to BGP in general, and the
  294.    use of TCP as the transport for BGP in particular, was its slow
  295.    convergence in presence of congestion.  This problem was experienced
  296.    in CA*Net. As we mentioned before, CA*Net is composed of 10 routers
  297.    that form a ring. The routers are connected by 56 Kbits/sec links.
  298.    All links are heavily utilized and are often congested.  Experience
  299.    with BGP in CA*Net showed that unless special measures are taken, the
  300.    protocol may exhibit slow convergence when BGP information is passed
  301.    over the slow speed (56 Kbits/sec) congested links. This is because a
  302.    large percentage of packets carrying BGP information are being
  303.    dropped due to congestion.  Therefore, there are three inter-related
  304.    problems: congestion, packet drops, and the resulting slow
  305.    convergence of routing under congestion and packet drops.
  306.  
  307.    Observe, that any transport protocol used by BGP would have
  308.    difficulty preventing packets from being dropped under congestion,
  309.    since it has no direct control over the routers that drop the
  310.    packets, and the congestion has nothing to do with the BGP traffic.
  311.    Therefore, since BGP is not the cause of congestion, and cannot
  312.    directly influence dropping at the routers, replacing TCP (as the BGP
  313.    transport) with another transport protocol would have no effect on
  314.    packets being dropped due to congestion. We think that once a network
  315.    is congested, packets will be dropped (regardless of whether these
  316.    packets carry BGP or any other information), unless special measures
  317.    outside of BGP in general, and the transport protocol used by BGP in
  318.    particular, are taken.
  319.  
  320.    If packets carrying routing information are lost, any distributed
  321.    routing protocol will exhibit slow convergence.  If quick convergence
  322.    is viewed as important for a routing within a network, special
  323.    measures to minimize the loss of packets that carry routing
  324.    information must be taken.  The next section suggests some possible
  325.    methods.
  326.  
  327. 9.3. Solutions to the problem.
  328.  
  329.    Two possible measures could be taken to reduce the drop of BGP
  330.    packets which slows convergence of routing:
  331.  
  332.       1) alleviate the congestion
  333.  
  334.       2) reduce the percentage of BGP packets that are dropped due
  335.  
  336.  
  337.  
  338. BGP Working Group                                               [Page 6]
  339.  
  340. RFC 1266            Experience with the BGP Protocol        October 1991
  341.  
  342.  
  343.          to congestion by marking BGP packets and setting policies to
  344.          routers to try not to drop BGP packets
  345.  
  346.    Alleviating the network congestion is a subject outside the control
  347.    of BGP, and will not be discussed in this paper.
  348.  
  349.    Operational experience with BGP in CA*Net shows that reducing the
  350.    percentage of BGP packets dropped due to congestion by marking them,
  351.    and setting policies to routers to try not to drop BGP packets
  352.    completely solves the problem of slow convergence in presence of
  353.    congestion.
  354.  
  355.    The BGP packets can be marked (explicitly or implicitly) by the
  356.    following three methods:
  357.  
  358.       a) by means of IP precedence (Internetwork Control)
  359.  
  360.       b) by using a well-known TCP port number
  361.  
  362.       c) by identifying packets by just source or destination IP
  363.          address.
  364.  
  365.    Appendix 4 of the BGP protocol specification, RFC 1163, recommends
  366.    the use of IP precedence (Internetwork Control) because the
  367.    precedence provides a well-defined mechanism to mark BGP packets.
  368.    The method of a well-known TCP port number to identify packets is
  369.    similar to the one that was used by Dave Mills in the NSFNET Phase I.
  370.    Dave Mills identified Telnet traffic by a well known TCP port number,
  371.    and gave it priority over the rest of the traffic.  CA*Net identified
  372.    BGP traffic based on it's source and destination IP address.  Packets
  373.    receive a priority if either the source or the destination IP address
  374.    belongs to CA*Net.
  375.  
  376.    If packets that carry the routing information are being dropped
  377.    (because of congestion), one also may ask about how does a particular
  378.    routing protocol react to such an event.  In the case of BGP the
  379.    packets are retransmitted using the TCP retransmission mechanism. It
  380.    seems plausible that being more aggressive in terms of the
  381.    retransmission should have positive effect on the convergence.  This
  382.    can be done completely within TCP by adjusting the TCP retransmission
  383.    timers. However, we would like to point out that the change in the
  384.    retransmission strategy should not be viewed as a cure for the
  385.    problem, since the root of the problem lies in the way how packets
  386.    that carry the BGP information are handled within a congested
  387.    network, and not in how frequently the lost packets are
  388.    retransmitted.
  389.  
  390.    It should also be pointed out that the local system can control the
  391.  
  392.  
  393.  
  394. BGP Working Group                                               [Page 7]
  395.  
  396. RFC 1266            Experience with the BGP Protocol        October 1991
  397.  
  398.  
  399.    amount of data to be retransmitted (in case of a congestion or
  400.    losses) by adjusting the TCP Window size. That allows to control the
  401.    amount of potentially obsolete data that has to be retransmitted.
  402.  
  403. 9.4. Perspective on the Convergence Problem.
  404.  
  405.    To put the convergence problem in a proper perspective, we'd like to
  406.    point out that much of the Internet now uses EGP at AS borders,
  407.    ensuring that routing changes cannot be guaranteed to propagate
  408.    between ASes in less than a few minutes. It would take huge amount of
  409.    congestion to slow BGP to this pace. Additionally, the problems of
  410.    EGP in the face of packet loss are well known and far exceed any
  411.    imaginable problem BGP/TCP might ever suffer.  Therefore, the worst
  412.    case behavior of BGP is about the same as the steady case behavior of
  413.    EGP.
  414.  
  415.    Within an AS the speed of convergence of the AS's IGP in the face of
  416.    congestion is of far greater concern than the propagation speed of
  417.    BGP, and indeed avoiding loss of packets carrying IGP, and a more
  418.    aggressive transport is similarly of much greater importance for an
  419.    IGP than for BGP.
  420.  
  421.    The issue of BGP convergence is of exaggerated importance to CA*Net
  422.    since CA*Net carries no information about external routes in its IGP.
  423.    CA*Net uses BGP to transfer external routes for use in computing
  424.    internal routes through the CA*Net network.  The reason CA*Net does
  425.    this has nothing to do with BGP. Under more ordinary circumstances an
  426.    IGP carries external routing information for use in computing
  427.    internal routes. CA*Net shows that BGP can work under extreme stress.
  428.    However, it's results should not be taken as the norm since most
  429.    networks will use BGP in a different (and less stressful)
  430.    configuration, where information about external routes will be
  431.    carried by an IGP.
  432.  
  433. 9.5. Conclusion.
  434.  
  435.    The extensive operational experience with BGP showed that the only
  436.    problem attributed to BGP was the slow convergence problem in
  437.    presence of congestion.  We demonstrated that this problem has
  438.    nothing to do with BGP in general, or with TCP as the BGP transport
  439.    in particular, but is directly related to the way how packets that
  440.    carry routing information are handled within a congested network. The
  441.    document suggests possible ways of solving the problem.  We would
  442.    like to point out that the issue of convergence in presence of
  443.    congested network is important to all distributed routing protocol,
  444.    and not just to BGP.  Therefore, we recommend that every routing
  445.    protocol (whether it is intra-autonomous system or inter-autonomous
  446.    system) should clearly specify how its behavior is affected by the
  447.  
  448.  
  449.  
  450. BGP Working Group                                               [Page 8]
  451.  
  452. RFC 1266            Experience with the BGP Protocol        October 1991
  453.  
  454.  
  455.    congestion in the networks, and what are the possible mechanisms to
  456.    avoid the negative effect of congestion (if any).
  457.  
  458. 10. Bibliography.
  459.  
  460.    [1] Hinden, B., "Internet Routing Protocol Standardization Criteria",
  461.        RFC 1264, BBN, October 1991.
  462.  
  463.    [2] Rekhter, Y., and P. Gross, "Application of the Border Gateway
  464.        Protocol in the Internet", RFC 1268, T.J. Watson Research Center,
  465.        IBM Corp., ANS, October 1991.
  466.  
  467.    [3] Lougheed, K., and Y. Rekhter, "A Border Gateway Protocol 3 (BGP-
  468.        3)", RFC 1267, cisco Systems, T.J. Watson Research Center, IBM
  469.        Corp., October 1991.
  470.  
  471.    [4] Willis, S., and J. Burruss, "Definitions of Managed Objects for
  472.        the Border Gateway Protocol (Version 3)", RFC 1269, Wellfleet
  473.        Communications Inc., October 1991.
  474.  
  475. Security Considerations
  476.  
  477.    Security issues are discussed in section 6.
  478.  
  479. Author's Address
  480.  
  481.    Yakov Rekhter
  482.    T.J. Watson Research Center IBM Corporation
  483.    P.O. Box 218
  484.    Yorktown Heights, NY 10598
  485.  
  486.    Phone:  (914) 945-3896
  487.    EMail: yakov@watson.ibm.com
  488.  
  489.    IETF BGP WG mailing list: iwg@rice.edu
  490.    To be added: iwg-request@rice.edu
  491.  
  492.  
  493.  
  494.  
  495.  
  496.  
  497.  
  498.  
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506. BGP Working Group                                               [Page 9]
  507.